package wodegua.d23_test.demo5;


/**
 * 需求:
 * 给你一个按照非递减顺序排列的整数数组 nums ，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值`target'，返回[-1，-1]。
 * 注意:必须确保程序的时间复杂度是o(log2n)，否则不给分数
 *
 * 具体功能点的要求如下:
 * 数组 nums =[5,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,10]，target =8
 * 得到结果是:[3,4]
 *
 * 数组:nums=[5,7,7,8,8,10]，target=6
 * 得到结果是:[-1，-1]
 *
 * 数组:nums=[]，target=0
 * 得到结果是:[-1，-1]
 *
 * 请设计一个方法完成以上需求，并编写测试代码完成上述测试，
 */
public class Test05 {
    public static void main(String[] args) {
        int[] nums1 = {5,7,7,8,8,10};
        int target1 = 8;
        run(nums1, target1);

        int[] nums2 = {5,7,7,8,8,10};
        int target2 = 6;
        run(nums2, target2);

        int[] nums3 = {};
        int target3 = 0;
        run(nums3, target3);

        int[] nums4 = {8,8,8,8,8,8,8,8,8,8,8,8,8,10};
        int target4 = 8;
        run(nums4, target4);


    }

    private static void run(int[] nums, int target){
        int left = getIndex(nums,target,true);
        int right = getIndex(nums,target,false);
//        System.out.println(left + "-" + right);
        StringBuilder s = new StringBuilder();
        s.append("[");
        if (right == -1) {
            s.append("-1, -1");
        } else {
            for (int i = left; i <= right; i++) {
                s.append(i);
                s.append(i == right ? "" : ", ");
            }
        }
        s.append("]");
        System.out.println(s);
    }

    private static int getIndex(int[] nums, int target,boolean flag){
        int left = 0;
        int right = nums.length - 1;
        int rs = -1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] < target) {
                left = middle + 1;
            } else if (nums[middle] > target) {
                right = middle - 1;
            } else {
                rs = middle;
                if (flag) {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }
        }
        return rs;
    }
}
